package org.example.myleet.linkedlist;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.ListNode;
import org.example.myleet.model.PrevNextListNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class LinkedListSolution {
    //p2
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //t进位，r当前位的计算结果，sum当前位的和
        int t = 0, r = 0, sum = 0;
        ListNode n1 = l1;
        ListNode n2 = l2;
        ListNode root = null;
        ListNode answer = null;
        while (null != n1 || null != n2 || t > 0) {
            //只要其中一个链表的节点还没完，或者还有进位没完，就继续叠新的位数
            sum = (null == n1 ? 0 : n1.val) + (null == n2 ? 0 : n2.val) + t;
            //如果sum大于9，则取余10得到个位数
            r = sum > 9 ? (sum % 10) : sum;
            if (null == answer) {
                //初始化
                answer = new ListNode(r);
                root = answer;
            } else {
                //叠新的节点到结果中
                answer.next = new ListNode(r);
                answer = answer.next;
            }
            //计算进位，供下一次循环用
            t = sum / 10;
            //两个输入链表前进游标，注意为空的情况
            n1 = null == n1 ? null : n1.next;
            n2 = null == n2 ? null : n2.next;
        }
        return root;
    }

    //p21
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                //其中之一为null，可直接截另一个列表剩下部分接上，因为是有序升序的
                cur.next = l2;
                break;
            } else if (l2 == null) {
                cur.next = l1;
                break;
            } else {
                if (l1.val < l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                } else {
                    cur.next = l2;
                    l2 = l2.next;
                }
            }
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 86【链表】分隔链表
     * O(n)
     * 0 ms
     */
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //用prev和next的技巧来"砍"出一个单独的prev节点
        ListNode prevNode = head, nextNode;
        //大于等于分区和小于分区分别用一个dummy和一个前驱节点来操作
        ListNode smallerDummy = new ListNode(-1), smallerNode = smallerDummy, biggerDummy = new ListNode(-1), biggerNode = biggerDummy;
        while (prevNode != null) {
            //"砍"出一个prev节点
            nextNode = prevNode.next;
            dummy.next = nextNode;
            prevNode.next = null;
            //观察prev大小，并分区，将分区的前驱节点往前移动
            if (prevNode.val < x) {
                smallerNode.next = prevNode;
                smallerNode = smallerNode.next;
            } else {
                biggerNode.next = prevNode;
                biggerNode = biggerNode.next;
            }
            prevNode = nextNode;
        }
        //最后拼接小于分区和大于等于分区
        if (smallerDummy.next == null) {
            dummy.next = biggerDummy.next;
        } else {
            dummy.next = smallerDummy.next;
            smallerNode.next = biggerDummy.next;
        }
        return dummy.next;
    }

    /**
     * 92【链表】反转链表 II
     * 0 ms
     * 考链表操作，拆链节点以及不同链表的接合
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //dummyHead是拆出来的新链的伪头，dummyHead2是原来的链的伪头，newLinkTail是新链的末尾
        ListNode dummyHead = new ListNode(-1), dummyHead2 = new ListNode(-1), newLinkTail, cur = head, prev, next;
        dummyHead2.next = head;
        prev = dummyHead2;
        //利用i标记让cur节点走到需要反转的节点起始位置
        int i = 1;
        while (i < left) {
            ++i;
            prev = cur;
            cur = cur.next;
        }
        //将cur从链表上切割下来，连接到dummyHead上
        if (cur != null) {
            prev.next = prev.next.next;
            cur.next = null;
        }
        dummyHead.next = cur;
        newLinkTail = cur;
        //从left到right扫描，逐个切割出cur并连接到紧跟dummyHead的位置，实现不断反转
        while (left < right && prev.next != null) {
            cur = prev.next;
            prev.next = prev.next.next;
            next = dummyHead.next;
            cur.next = next;
            dummyHead.next = cur;
            ++left;
        }
        //最后将新链的尾部连接到旧链切割出来到尾巴，旧链的头部连接到新链上，完整left到right部分反转
        if (newLinkTail != null) {
            newLinkTail.next = prev.next;
        }
        prev.next = dummyHead.next;
        return dummyHead2.next;
    }

    /**
     * 138【链表巧妙操作】复制带随机指针的链表
     * 官方解答思路
     * 使用一个小技巧来省去哈希表的空间
     * 三次遍历
     * 我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′（第一次遍历链表）
     * 然后第二次遍历链表时，每次处理两个节点，例如A→A′，从A可以找到random节点，则random′节点就是A′的random指针指向的节点，第二遍是补充拷贝节点的random指针
     * 第三次遍历时将拷贝的节点取出连接成结果A′→B′→C′，并还原入参链表A→B→C，
     */
    static class Node138 {
        int val;
        Node138 next;
        Node138 random;

        public Node138(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node138 copyRandomList(Node138 head) {
        if (head == null) {
            return null;
        }
        Node138 dummy = new Node138(-1), curSource = head, curTarget = dummy;
        //第一次遍历，拷贝和拆分节点
        while (curSource != null) {
            Node138 sourceNext = curSource.next;
            curSource.next = new Node138(curSource.val);
            curSource.next.next = sourceNext;
            curSource = sourceNext;
        }
        //第二次遍历，补充random指针
        curSource = head;
        while (curSource != null) {
            Node138 rand = curSource.random;
            Node138 target = curSource.next;
            if (rand != null) {
                target.random = rand.next;
            }
            curSource = curSource.next.next;
        }
        //第三次遍历，整理两个链表，将拷贝的节点取出连接成结果A′→B′→C′，并还原入参链表A→B→C
        curSource = head;
        while (curSource != null) {
            Node138 target = curSource.next;
            curSource.next = target.next;
            curSource = curSource.next;
            curTarget.next = target;
            curTarget = curTarget.next;
        }
        return dummy.next;
    }

    /**
     * 146【双向链表+哈希表】LRU 缓存
     */
    static class LRUCache {
        static class DualDirNode {
            DualDirNode prev;
            DualDirNode next;
            int key;
            int val;

            public DualDirNode(int k, int v) {
                key = k;
                val = v;
            }

//            @Override
//            public String toString() {
//                final StringBuilder sb = new StringBuilder("");
//                DualDirNode cur = this;
//                while (null != cur) {
//                    sb.append("{k=").append(cur.key);
//                    sb.append(", v=").append(cur.val);
//                    sb.append('}').append(',');
//                    cur = cur.next;
//                }
//                return sb.toString();
//            }
        }

        private final DualDirNode head;
        private final DualDirNode tail;

        private int size;

        private final int cap;

        private Map<Integer, DualDirNode> keyMapNode;

        public LRUCache(int capacity) {
            keyMapNode = new HashMap<>(capacity);
            head = new DualDirNode(-1, -1);
            tail = new DualDirNode(-1, -1);
            head.next = tail;
            size = 0;
            cap = capacity;
        }
        public int get(int key) {
            if (keyMapNode.containsKey(key)) {
                DualDirNode node = keyMapNode.get(key);
                //move to head
                moveToHead(node);
                return node.val;
            }
            return -1;
        }
        public void put(int key, int value) {
            DualDirNode node;
            if (keyMapNode.containsKey(key)) {
                //key已存在，刷新val，并移到头部（最新使用过）
                node = keyMapNode.get(key);
                node.val = value;
                moveToHead(node);
            } else {
                if (size < cap) {
                    //key不存在，且未达到缓存的最大空间，直接新建节点插入到队列头部
                    node = new DualDirNode(key, value);
                    DualDirNode next = head.next;
                    head.next = node;
                    node.prev = head;
                    node.next = next;
                    next.prev = node;
                    keyMapNode.put(key, node);
                    ++size;
                } else {
                    //key不存在，LRU删除队列尾部结点，回收这个结点，刷新key和val，并移到头部（最新使用过）
                    node = tail.prev;
                    keyMapNode.remove(node.key);
                    node.key = key;
                    node.val = value;
                    moveToHead(node);
                    keyMapNode.put(key, node);
                }
            }
        }
        /**
         * 将node从链表中的某个位置移到链表头部
         */
        private void moveToHead(DualDirNode node) {
            //将node的前后结点取出
            DualDirNode prev = node.prev;
            DualDirNode next = node.next;
            //将node的前后结点连在一起
            prev.next = next;
            next.prev = prev;
            //取出head的next结点，将node插入到head和next之间
            next = head.next;
            head.next = node;
            node.prev = head;
            node.next = next;
            next.prev = node;
        }
    }

    /**
     * 147【链表操作】对链表进行插入排序
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode curNode = head;
        while (curNode != null) {
            if (curNode.next != null) {
                ListNode candidate = curNode.next;
                //检查是不是升序的
                if (candidate.val < curNode.val) {
                    //如果不是升序就执行插入排序，下面是从头到尾找到合适的插入位置
                    ListNode newHead = head;
                    //curNode > candidate，要找到candidate应该插入的位置
                    ListNode cur = newHead;
                    while (true) {
                        if (cur.next == null) {
                            //end
                            break;
                        }
                        if ((cur.val <= candidate.val && cur.next.val >= candidate.val)) {
                            //找到合适candidate的位置了，n <= candidate <= n.next，将candidate抽出来
                            curNode.next = candidate.next;
                            //临时保存n.next
                            ListNode t = cur.next;
                            //将candidate放到n后面
                            cur.next = candidate;
                            //将原来的n.next放到candidate后面，完成candidate插入到n与n.next之间
                            candidate.next = t;
                            break;
                        } else if (candidate.val < newHead.val) {
                            //这种情况下则是换头，candidate需要放到head前面成为newHead
                            curNode.next = curNode.next.next;
                            candidate.next = newHead;
                            newHead = candidate;
                            break;
                        }
                        cur = cur.next;
                    }
                    //一次插入完成，更新head
                    head = newHead;
                    continue;
                }
            }
            curNode = curNode.next;
        }
        return head;
    }

    /**
     * 189【链表模拟】轮转数组
     * 2 ms
     * 用链表操作，但是非原地算法
     */
    public void rotate(int[] nums, int k) {
        if (k >= nums.length) {
            k = k % nums.length;
        }
        if (k == 0) {
            return;
        }
        PrevNextListNode dummy = new PrevNextListNode(-1);
        PrevNextListNode cur = dummy;
        for (int i : nums) {
            cur.next = new PrevNextListNode(i);
            cur.next.prev = cur;
            cur = cur.next;
        }
        PrevNextListNode end = cur;
        PrevNextListNode start = cur;
        for (int i=1; i<k; i++) {
            start = cur.prev;
            cur = start;
        }
        cur.prev.next = null;
        end.next = dummy.next;
        dummy.next.prev = end;
        dummy.next = start;
        start.prev = dummy;
        int i=0;
        cur = dummy.next;
        while (cur != null) {
            nums[i++] = cur.val;
            cur = cur.next;
        }
    }

    /**
     * 203【链表操作】移除链表元素
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (cur != null) {
            if (cur.next != null && cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 206【链表操作】反转链表
     * 不断地紧跟dummy插入head的顺序遍历的结点即可完成反转链表
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            ListNode newHead = dummy.next;
            dummy.next = cur;
            if (newHead != null) {
                dummy.next.next = newHead;
            }
            cur = curNext;
        }
        return dummy.next;
    }

    /**
     * 460【双向链表+哈希表】LFU 缓存
     */
    static class LFUCache {
        static class DualDirNode {
            DualDirNode prev;
            DualDirNode next;
            int key;
            int val;
            int cnt;
            public DualDirNode(int k, int v) {
                key = k;
                val = v;
                cnt = 1;
            }

            @Override
            public String toString() {
                final StringBuilder sb = new StringBuilder("");
                sb.append("{k=").append(key);
                sb.append(", v=").append(val);
                sb.append(", cnt=").append(cnt);
                sb.append('}');
                return sb.toString();
            }
        }
        final int cap;
        int minCnt;

        //保存key到单个DualDirNode的映射
        Map<Integer, DualDirNode> keyMapNode;

        //保存操作数cnt到DualDirNode双向链表的映射
        Map<Integer, DualDirNode> cntMapNode;

        public LFUCache(int capacity) {
            keyMapNode = new HashMap<>(capacity);
            cntMapNode = new HashMap<>(capacity);
            cap = capacity;
        }
        public int get(int key) {
            DualDirNode node = getNode(key);
            if (node != null) return node.val;
            return -1;
        }
        public void put(int key, int value) {
            DualDirNode node = getNode(key);
            if (null != node) {
                //key已存在，刷新val
                node.val = value;
                return;
            }
            if (keyMapNode.size() == cap) {
                //缓存大小已经达到最大值，移除一个操作数最小的结点
                DualDirNode dummy = cntMapNode.get(minCnt);
                //获取最小操作数中最久未使用的结点（双向链表中的最后一个结点）
                DualDirNode prev = dummy.prev;
                //两个哈希表中均需移除这个结点
                keyMapNode.remove(prev.key);
                removeNode(prev);
                if (dummy.next == dummy) {
                    //如果minCnt操作数对应的双向链表空了，则移除此操作数对应的双向链表
                    cntMapNode.remove(minCnt);
                }
            }
            //新建一个结点并插入到操作数为1的双向链表中
            node = new DualDirNode(key, value);
            pushFront(1, node);
            minCnt = 1;
        }
        private DualDirNode getNode(int key) {
            //如果keyMapNode没有就是没有了
            if (!keyMapNode.containsKey(key)) return null;
            //由于进行了get操作，因此需要+1操作数，将这个结点从其操作数的双向链表中移除
            DualDirNode node = keyMapNode.get(key);
            DualDirNode dummy = cntMapNode.get(node.cnt);
            removeNode(node);
            if (dummy.next == dummy) {
                //如果node.cnt操作数对应的双向链表空了，则移除此操作数对应的双向链表
                cntMapNode.remove(node.cnt);
                if (minCnt == node.cnt) ++minCnt;
            }
            //增加node的操作数
            node.cnt++;
            //将node插入到node.cnt操作数对应的双向链表的头部
            pushFront(node.cnt, node);
            return node;
        }
        private void removeNode(DualDirNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        private void pushFront(int cnt, DualDirNode node) {
            DualDirNode dummy = cntMapNode.get(cnt);
            if (null == dummy) {
                //cnt操作数对应的双向链表不存在，新建一个
                dummy = new DualDirNode(-1, -1);
                dummy.next = dummy;
                cntMapNode.put(cnt, dummy);
            }
            //将node插入到dummy的下一个节点完成插入到双向链表头部的动作
            node.next = dummy.next;
            dummy.next.prev = node;
            dummy.next = node;
            node.prev = dummy;
            //记录这个node的快捷路径
            keyMapNode.put(node.key, node);
        }
    }

    /**
     * 706【取余哈希+链表】设计哈希映射
     */
    static class MyHashMap {
        private static final int BASE = 1021;
        private List<int[]>[] map;
        public MyHashMap() {
            map = new LinkedList[BASE];
        }

        public void put(int key, int value) {
            int idx = key % BASE;
            List<int[]> slot = map[idx];
            if (null == slot) {
                map[idx] = new LinkedList<>();
                slot = map[idx];
            }
            boolean updated = false;
            for (int[] i : slot) {
                if (i[0] == key) {
                    i[1] = value;
                    updated = true;
                }
            }
            if (!updated) slot.add(new int[]{key, value});
        }

        public int get(int key) {
            int idx = key % BASE;
            List<int[]> slot = map[idx];
            if (null == slot) return -1;
            for (int[] i : slot) {
                if (i[0] == key) {
                    return i[1];
                }
            }
            return -1;
        }

        public void remove(int key) {
            int idx = key % BASE;
            List<int[]> slot = map[idx];
            if (null == slot) return;
            for (int[] i : slot) {
                if (i[0] == key) {
                    i[1] = -1;
                    return;
                }
            }
        }
    }

    //p1823
    /**
     * 链表模拟
     */
    public int findTheWinner(int n, int k) {
        Node1823 dummyHead = new Node1823(-1);
        Node1823 cur = dummyHead, prev;
        for (int i = 1; i <= n; ++i) {
            cur.next = new Node1823(i);
            cur = cur.next;
        }
        //成环
        cur.next = dummyHead.next;
        //prev初始为节点n
        prev = cur;
        //循环结束的条件是整个环只剩1个元素
        while (cur.val != cur.next.val) {
            //向前走k步
            for (int i = 0; i < k; ++i) {
                prev = cur;
                cur = cur.next;
            }
            //走完k步，找到需要移除的节点，从链表中移除
            prev.next = cur.next;
            cur.next = null;
            cur = prev;
        }
        return cur.val;
    }

    public static class Node1823 {
        int val;
        Node1823 next;

        public Node1823(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Node{");
            sb.append("val=").append(val);
            sb.append('}');
            return sb.toString();
        }
    }

    /**
     * 2296【双向链表】设计一个文本编辑器
     */
    static class TextEditor {
        class Node {
            Node prev;
            Node next;
            char ch;
            public Node(char ch) {
                this.ch = ch;
            }
//            @Override
//            public String toString() {
//                Node cur = this;
//                StringBuilder leading = new StringBuilder();
//                while (dummyTail != cur) {
//                    cur = cur.next;
//                    leading.append(cur.ch);
//                }
//                cur = this;
//                StringBuilder previous = new StringBuilder();
//                previous.append(cur.ch);
//                while (dummyHead != cur) {
//                    cur = cur.prev;
//                    previous.append(cur.ch);
//                }
//                return previous.reverse() + "|" + leading.toString();
//            }
        }
        private final Node dummyHead;
        private final Node dummyTail;
        private Node curr; //光标指向的字符，光标在字符右边

        private String getLeftString() {
            if (dummyHead == curr) return "";
            Node cur = curr;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 10; ++i) {
                if (dummyHead == cur) break;
                sb.append(cur.ch);
                cur = cur.prev;
            }
            return sb.reverse().toString();
        }

        public TextEditor() {
            dummyHead = new Node('-');
            dummyTail = new Node('-');
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
            curr = dummyHead;
        }

        public void addText(String text) {
            for (char c : text.toCharArray()) {
                Node insertNode = new Node(c);
                insertNode.next = curr.next;
                insertNode.prev = curr;
                curr.next.prev = insertNode;
                curr.next = insertNode;
                curr = curr.next;
            }
        }

        public int deleteText(int k) {
            int deleteCnt = 0;
            for (int i = 0; i < k; ++i) {
                if (dummyHead == curr) break;
                Node prev = curr.prev;
                prev.next = curr.next;
                curr.next.prev = prev;
                curr = curr.prev;
                ++deleteCnt;
            }
            return deleteCnt;
        }

        public String cursorLeft(int k) {
            for (int i = 0; i < k; ++i) {
                if (dummyHead == curr) break;
                curr = curr.prev;
            }
            return getLeftString();
        }

        public String cursorRight(int k) {
            for (int i = 0; i < k; ++i) {
                if (dummyTail == curr.next) break;
                curr = curr.next;
            }
            return getLeftString();
        }
    }

    public static void main(String[] args) {
        TextEditor textEditor = new TextEditor();
        textEditor.addText("mjzxkemqyvfrg");
        Assert.isTrue("mjzxkemq".equals(textEditor.cursorLeft(5)));
        textEditor.addText("svvyobqebssp");
        textEditor.addText("xkoznsq");
        Assert.isTrue("xkoznsqyvf".equals(textEditor.cursorRight(3)));
    }
}
